package com.xiaoyu.linkedArray;

/**
 * @program: DS_and_A
 * @description: 排序链表
 *
 * 给你链表的头结点head，请将其按 升序 排列并返回 排序后的链表 。
 * 进阶：
 * 你可以在O(nlogn) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
 *
 * 输入：head = [4,2,1,3]
 * 输出：[1,2,3,4]
 *
 * @author: YuWenYi
 * @create: 2021-06-01 11:33
 **/
public class SortList_148 {

    public ListNode sortList1(ListNode head) {
        return quickSort(head, null);
    }
    //快排方式,不是很好,因为如果链表已经有序那么时间复杂度将退化成O(n^2)
    public ListNode quickSort(ListNode head,ListNode tail) {
        if (head == tail || head.next == tail) return head;  //特判,只有一个元素或者没有元素
        //假设left维护的是小于基准值的头插指针，right维护的是大于等于基准值的尾插指针
        ListNode left = head,right = head,p = head.next;
        while (p !=  tail){
            ListNode next = p.next;
            if (p.val < left.val){  //采用头插法
                p.next = left;
                left = p;
            }else {   //采用尾插法
                right.next = p;
                right = p;
            }
            p = next;
        }
        right.next = tail;
        ListNode node = quickSort(left, head);
        head.next =  quickSort(head.next, tail);
        return node;
    }

    /**
     * 参考：Sort List——经典（链表中的归并排序） https://www.cnblogs.com/qiaozhoulin/p/4585401.html
     *
     * 归并排序法：利用归并的思想，递归地将当前链表分为两段，然后merge，分两段的方
     * 法是使用 fast-slow 法，用两个指针，一个每次走两步，一个走一步，直到快的走到了末尾，然后
     * 慢的所在位置就是中间位置，这样就分成了两段。merge时，把两段头部节点值比较，用一个 p 指向
     * 较小的，且记录第一个节点，然后 两段的头一步一步向后走，p也一直向后走，总是指向较小节点，
     * 直至其中一个头为NULL，处理剩下的元素。最后返回记录的头即可。
     *
     * 主要考察3个知识点，
     * 知识点1：归并排序的整体思想
     * 知识点2：找到一个链表的中间节点的方法
     * 知识点3：合并两个已排好序的链表为一个新的有序链表
     */

    //归并排序去对链表排序才是最优解!
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;  //特判,只有一个元素或者没有元素

        return cutHalf(head);
    }

    //将链表切一半
    public ListNode cutHalf(ListNode head) {
        //只要将链表切成单独的了,那么就去将它们合并!
        if (head.next == null) return head;

        ListNode fast = head,slow = head,pre = head;

        while (fast!=null && fast.next!=null){
            pre = slow;
            fast = fast.next.next;
            slow = slow.next;
        }
        pre.next = null;   //断前半截链表的尾巴!

/*        System.out.print("head:");
        ListNode.printList(head);
        System.out.print("slow:");
        ListNode.printList(slow);*/

        //先切左边,直到切完了之后再去切右边
        ListNode l = cutHalf(head);
        ListNode r = cutHalf(slow);

/*        System.out.print("l:");
        ListNode.printList(l);
        System.out.print("r:");
        ListNode.printList(r);*/

        return merge(l, r);
    }


    public ListNode merge(ListNode l,ListNode r){
        ListNode dummy = new ListNode(0);
        ListNode p = dummy;

        while (l != null && r != null){
            if (l.val < r.val){
                p.next = l;
                l = l.next;
            }else {
                p.next = r;
                r = r.next;
            }
            p = p.next;
        }
        if (l != null){
            p.next = l;
        }
        if (r != null){
            p.next = r;
        }

        return dummy.next;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1,new ListNode(2,
                new ListNode(3,new ListNode(4,new ListNode(8,
                        new ListNode(7,new ListNode(6,new ListNode(5))))))));

        SortList_148 list148 = new SortList_148();
        ListNode res = list148.sortList(head);

        ListNode.printList(res);
    }
}
